import java.util.*;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字典顺序排序
 * 链接：https://leetcode.cn/problems/top-k-frequent-words
 *
 * 输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
 * 输出: ["i", "love"]
 * 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
 *     注意，按字母顺序 "i" 在 "love" 之前。
 */
@SuppressWarnings({"all"})
class Solution {

    // 算法逻辑代码
    public List<String> topKFrequent(String[] words, int k) {
        List<String> res = new LinkedList<>(); // 用于存储结果
        // 1. 先统计每个单词出现的次数
        Map<String, Integer> countMap = new HashMap<>();
        for(String word : words){
            countMap.put(word, countMap.getOrDefault(word, 0)+1);
        }
        // 2. 由于是求前k个出现次数最多的单词，所以使用小根堆，每次与堆顶进行比较
        PriorityQueue<Map.Entry<String, Integer>> minLeap = new PriorityQueue<>(
                new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    // 如果频率相同 则根据字典序进行调整
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        // 3. 维护小根堆
        for(Map.Entry<String, Integer> entry : countMap.entrySet()){
            if (k-- > 0){
                // 先存入前k个
                minLeap.offer(entry);
            }else {
                // 根据频率进行存储
                if (minLeap.peek().getValue().compareTo(entry.getValue()) < 0){
                    // 如果下一个单词出现的频率大于堆顶，则替换
                    minLeap.poll();
                    minLeap.offer(entry);
                }else if (minLeap.peek().getValue().equals(entry.getValue())){
                    // 如果频率相同，则根据字典序进行处理
                    if (minLeap.peek().getKey().compareTo(entry.getKey()) > 0){
                        minLeap.poll();
                        minLeap.offer(entry);
                    }
                }
            }
        }
        // 4. 将结果存入list中，最后返回反转后的结果
        while (!minLeap.isEmpty()){
            Map.Entry<String, Integer> pollEntry = minLeap.poll();
            res.add(pollEntry.getKey());
        }
        Collections.reverse(res);
        return res;
    }

    // 用于测试
    public static void main(String[] args) {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 2;
        List<String> list = new Solution().topKFrequent(words, k);
        System.out.println(list);
    }
}
